package toOffer;

/**
 * <h3>toOffer</h3>
 *
 * @author YuanAo
 * @date 2024/5/24 14:36
 * @description <p>x的平方根</p>
 */

/**
 * 题目：
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 * 示例 1：
 * <p>
 * 输入：x = 4
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 */
public class No69 {
    public static void main(String[] args) {
        int x = 2147395599;
        System.out.println(mySqrt(x));
    }

    /**
     * 思路： 知道这公式、这题就是简单题，不知道那就麻烦了、算小中等题
     * X(n+1) = (X(n)+a/X(n))/2
     *
     * 需要注意一下：long和int类型，题目给的int但是如果你用int来判断比较的话是不行的（试过会报错），必须要转成long去比较、最后返回的时候再从long转回int
     * 原则上说long转int会有数据的损失，但是由于他给的就是int，int数据的平方根肯定也是int类型不会溢出
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
        long i = x;
        while (i * i > x) {
            i = (i + x / i) / 2;
        }
        return (int)i;
    }
}


